<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        function TreeNode(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        let a = new TreeNode(1)
        let b = new TreeNode(3)
        let c = new TreeNode(2)
        let d = new TreeNode(5)
        a.left = b
        a.right = c
        b.left = d

        let aa = new TreeNode(2)
        let bb = new TreeNode(1)
        let cc = new TreeNode(3)
        let dd = new TreeNode(4)
        let ee = new TreeNode(7)
        aa.left = bb
        aa.right = cc
        bb.right = dd
        cc.right = ee
        /* 
        时间O(n) n是节点的个数，while循环的次数
        空间O(n) n是队列数组占用的空间
        思路：利用迭代，两棵树的目标节点 放进queue，取出判断，值相加 + 判断左右节点是否为null
            如果左节点和右节点都不为null 就直接放入queue 下次判断
            如果左节点为null 右节点不为null 就直接赋值
            如果左节点和右节点都为null 就不管了
        */
        var mergeTrees = function (root1, root2) {
            // 1. 判空 【想不到的点】
            if (root1 === null) return root2
            if (root2 === null) return root1
            // 2. 创建队列 队列初始化【一个队列就够了】
            let queue = []
            queue.push(root1)
            queue.push(root2)
            // 3. while循环 
            // 【每次while循环 能够搞定当前的节点 以及下面的左右节点 
            // 1 node1和node2 都不为null 就push 进入queue下次while循环搞定 
            // 2 node1为null node2不为null 就直接赋值 
            // 3 都是null就不用管了】
            while (queue.length > 0) {
                // 4. while循环里面刚进去的 一定都是不为空的 root1.val += 若roo2.val
                let node1 = queue.shift()
                let node2 = queue.shift()
                node1.val += node2.val
                // 5. 如果node1的左节点和node2的左节点都不为空 就加入队列
                if (node1.left !== null && node2.left !== null) {
                    queue.push(node1.left)
                    queue.push(node2.left)
                }

                // 6. 如果node1的右节点和node2的右节点都不为空 就加入队列
                if (node1.right !== null && node2.right !== null) {
                    queue.push(node1.right)
                    queue.push(node2.right)
                }
                // 7. 如果node1的左节点为空  但是node2的左节点不为空 直接赋值
                if (node1.left === null && node2.left !== null) {
                    node1.left = node2.left
                }

                // 8. 如果node1的右节点为空  但是node2的右节点不为空 直接赋值
                if (node1.right === null && node2.right !== null) {
                    node1.right = node2.right
                }
            }
            // 9. 返回root1节点
            return root1
        };
        console.log(mergeTrees(a, aa));
    </script>
</body>

</html>